home *** CD-ROM | disk | FTP | other *** search
/ Scene 96 / Scene 96 International Edition (Zyklop Software) (Disc 2) (1997).iso / misc / coding / flc_bsrt / bytesort.txt next >
Text File  |  1996-06-12  |  10KB  |  309 lines
  1.                    Comment trier ses donnees vite et bien ?
  2.                   Le Byte Sort, algorithme de tri efficace.
  3.  
  4.                        (c) Mai 1996 Phar /Flower Corp
  5.                       contact : souiki@fiifo.u-psud.fr
  6.               Juillet et Aout : Flower.Corp@ace.epita.fr
  7.  
  8. Si vous avez des questions concernant le present document, n'hesitez pas a
  9. m'envoyer un mail, ou a me parler sur IRC sur #demofr
  10.  
  11.  
  12. I Presentation
  13. --------------
  14.  
  15. Maintenant que la 3D est vraiment a la mode, tout le monde parle de trier
  16. les faces des objets. Et ici, on observe tres vite que chacun prefere un
  17. algorithme de tri different. Toutefois, on observe 2 grandes tendances :
  18. le Radix Sort, ou le Quick Sort (tri par tas ou tri rapide), qui ont tous
  19. les deux l'avantage d'etre rapides. Neanmoins, dans des applications comme
  20. les demos, ou la rapidite est vraiment l'element le plus important, ces
  21. deux tris souffrent de leurs tares : ils sont trop generaux : il conviennent
  22. a n'importe quel type de donnee (pour le quick sort en tout cas).
  23.  
  24. Le Byte sort est un algorithme inspire tout droit du Radix sort, mais
  25. il a 2 enormes avantages : il est facile a coder, et il est tres rapide.
  26. Facile a coder, nous allons le voir, puisque son algo est tres simple.
  27. Tres rapide, puisque c'est un tri en N, et non en N Log N.
  28.  
  29.  
  30. II Principe de base
  31. -------------------
  32.  
  33. Quel est le principe de base du Byte Sort ?? C'est tout simplement de ne
  34. faire AUCUNE comparaison. Tout notre travail va etre de savoir OU placer
  35. la donnee, et c'est tout.
  36.  
  37. On va donc travailler en 3 etapes :
  38. * La premiere, va etre de compter le nombre d'occurrences de chaque nombre,
  39.   c'est a dire : combien de fois j'ai la valeur 28 par exemple.
  40.  
  41. * La deuxieme, va etre de transformer ces occurrences en position : pour
  42.   cela, on va balayer notre tableau qui contient les comptages, et on
  43.   va le transformer en un tableau qui donne les adresses.
  44.  
  45. * La troisieme, va etre de prendre nos valeurs, et les positionner la ou
  46.   il faut dans un autre tableau, qui sera donc trie.
  47.  
  48. On le voit donc, il n'y a pas de comparaisons! Juste des positions...
  49. Cela fait que chacune des trois etapes se code en quelques lignes d'assembleur.
  50.  
  51. Pour faire ce tri, on a donc besoin des ingredients suivants :
  52. Un bouquet garni.
  53. Un processeur.
  54. 250g de beurre pour 8 personnes.
  55. Plus :
  56. Un tableau qui contient les donnees.
  57. Un tableau qui contient les adresses.
  58. Un tableau qui contiendra les donnees triees.
  59.  
  60. Pour les programmeurs PC en mode 32 bits, on pourrait dire :
  61. Tableau de 1 a N de Structures  <= Tableau non Trie, de N faces
  62.     Numero de Face : Entier 32 bits
  63.     Valeur du Z    : Entier 32 bits
  64.  
  65. Tableau de 0 a 255 de           <= Tableau pour les positions
  66.     Nombre : Entier 32 bits
  67.  
  68. Tableau de 1 a N de             <= Tableau Trie de N faces
  69.     Numero de Face
  70.  
  71.  
  72.  
  73.  
  74. III Le fonctionnement
  75. ---------------------
  76.  
  77. Nous avons donc Notre Tableau1, qui contient les donnees a trier.
  78. On va trier ce tableau en 4 passes : on va trier les octets 1,2,3 puis 4
  79. (note : cela marche aussi dans l'autre sens, car le tri est sequentiel :
  80. pour 2 memes valeurs, il ne change pas l'ordre).
  81.  
  82. <--- 32 bits --->
  83.  _______________
  84. |   |   |   |   |
  85. | 1 | 2 | 3 | 4 |
  86. |___|___|___|___|
  87.  
  88. Nous verrons au dernier chapitre comment faire en moins de passes...(patience)
  89.  
  90. Bien, maintenant que nous savons que nous allons trier en 4 passes, voyons
  91. chacune des 3 etapes qui composent notre tri :
  92.  
  93.  
  94. A) Etape I : la creation du tableau 2.
  95. --------------------------------------
  96.  
  97. Dans un premier temps, on va initialiser le tableau 2 a zero :
  98. Pour i=0 a 255 faire
  99.   Tab2[i]=0;
  100.  
  101. Nous allons ensuite parcourir les cases de notre tableau 1 (celui a trier) une
  102. par une. Pour chaque case, on va recuperer la valeur.
  103. Ensuite, comme vu plus haut, nous allons indiquer dans le tableau 2, que cette
  104. valeur a ete vue une fois de plus. La boucle est donc :
  105.  
  106. Pour i=0 a n-1 faire
  107.    val=octet(Tab1[i].Z);         /* On recupere la coordonnee. */
  108.    Tab2[val]=Tab2[val]+1;
  109.  
  110.  
  111. A la fin de cette premiere etape, le tableau 2 contient le nombre de fois
  112. ou on a vu chaque octet.
  113.  
  114. Exemple :
  115. Soit le tableau 1 :
  116.  
  117. indice 0 1 2 3 4 5 6 7
  118. ------------------------
  119. valeur 2 4 6 3 2 4 5 1
  120.  
  121.  
  122. Le tableau 2 correspondant (ou tout du moins son debut) sera :
  123.  
  124. indice 0 1 2 3 4 5 6 7 8
  125. ------------------------
  126. valeur 0 1 2 1 2 1 1 0 0
  127.  
  128.  
  129.  
  130. B) Etape II : Transformation du tableau 2.
  131. ------------------------------------------
  132.  
  133. Nous avons donc dans le tableau 2 le nombre d'occurences de chaque valeur.
  134. Celles-ci vont nous permettre de connaitre la position de chaque valeur.
  135. En effet, il suffit de parcourir notre tableau 2, puis de calculer la nouvelle
  136. position. Celle-ci se deduit de la precedente, puis on ajoute le nombre
  137. d'occurences courant. Voyons l'algo :
  138.  
  139. position=0
  140. Pour i=0 a 255 faire
  141.    increment=Tab2[i]
  142.    Tab2[i]=position
  143.    position=position+increment
  144.  
  145. Donc, si on applique cette boucle a l'exemple precedent, on trouve:
  146.  
  147. indice   0  1  2  3  4  5  6  7  8
  148. ---------------------------------
  149. valeur   0  0  1  3  4  6  7  8  8
  150.  
  151.  
  152. Qu'est-ce que cela veut dire ??? Et bien tout simplement que l'emplacement
  153. de depart des donnees dont la valeur est 1 sera la case 0. Ou que l'emplacement
  154. de depart des donnees dont la valeur est 6 sera la case 7.
  155. C'est magique! C'est Fantastique! (envoyez vos dons a Phar, C.C.P 148691738)
  156.  
  157. Bien, il nous reste a regler un dernier point de detail (mineur), le tri
  158. de nos donnees :
  159.  
  160.  
  161.  
  162. C) Etape III : Tri des donnees, du tableau 1 au tableau 3.
  163. ----------------------------------------------------------
  164.  
  165. Il nous reste finalement a trier les donnees, et on va encore effectuer une
  166. boucle. En fait, pour chaque case de notre tableau initial, nous allons
  167. recuperer la valeur de l'octet voulu. Nous allons chercher dans le tableau 2
  168. quelle est la position ou il faut mettre cette valeur. Et on va mettre notre
  169. donnee a la bonne position du tableau 3.
  170.  
  171. 2 remarques :
  172. 1) pour ne pas ecraser les donnees du tableau 1, on utilise un 3eme tableau,
  173.    qui contiendra donc les donnees triees.
  174.  
  175. 2) Il faut aussi gerer le fait que l'on avance dans notre tableau 3 : si l'on
  176.    trouve la valeur 3, puis que l'on retrouve une autre fois la valeur 3, il
  177.    fait que la position ait avance d'une case. Donc, a chaque fois que l'on
  178.    recupere une position dans le tableau 2, on incremente la case.
  179.  
  180. Tout cela donne l'algo suivant :
  181.  
  182. Pour i=0 a N-1 faire :
  183.  
  184.    val=octet(Tab1[i].Z);      /* on recupere la clef de tri. */
  185.  
  186.    pos=tab2[val];             /* on en deduit la position. */
  187.    tab2[val]=tab2[val]+1;
  188.  
  189.    tab3[pos]=Tab1[i].Numero_de_face /* on place la donnee a la bonne pos*/
  190.  
  191.  
  192. Et si, une fois encore, on reprend l'exemple, on avait :
  193.  
  194. Tableau 1 =
  195.  
  196. indice 0 1 2 3 4 5 6 7
  197. ------------------------
  198. valeur 2 4 6 3 2 4 5 1
  199.  
  200.  
  201. Tableau 2 =
  202.  
  203. indice   0  1  2  3  4  5  6  7  8
  204. ---------------------------------
  205. valeur   0  0  1  3  4  6  7  8  8
  206.  
  207.  
  208. Donc, Tableau 3=
  209.  
  210. indice   0  1  2  3  4  5  6  7
  211. --------------------------------
  212. valeur   7  0  4  3  1  5  6  2
  213.  
  214. Et on voit le resultat :
  215. On a un fabuleux tableau trie! (sisi, verifiez!! il est trie!)
  216.  
  217. Donc, on vient de trier un tableau en 200 lignes de texte, mais sans aucune
  218. comparaison
  219.  
  220.  
  221.  
  222.  
  223. IV Precisions
  224. --------------
  225.  
  226. L'algo, tel que je vient de l'expliquer, marche tres bien, mais il ne faut
  227. pas oublier qu'il faut l'effectuer 4 fois, pour 4 octets... (32 bits),
  228. chaque fois sur un octet different.
  229. De plus, la premiere passe se fait en transformant le tableau 1 en tableau 3,
  230. mais a la 2eme etape, il faudra reutiliser les donnees contenues dans le
  231. tableau 3!!
  232. Donc, passes 1 et 3 : Tab1 => Tab3
  233.              2    4 : Tab3 => Tab1 (pour ne pas consommer trop de memoire)
  234.  
  235.  
  236. Revoyons l'algo au complet :
  237.  
  238. A chaque Passe, octet(x), donne l'octet de x que l'on souhaite trier.
  239.  
  240. /* Etape I */
  241.  
  242. Pour i=0 a n-1 faire
  243.    val=octet(Tab1[i].Z);         /* On recupere la coordonnee. */
  244.    Tab2[val]=Tab2[val]+1;
  245.  
  246.  
  247. /* Etape II */
  248.  
  249. position=0
  250. Pour i=0 a 255 faire
  251.    increment=Tab2[i]
  252.    Tab2[i]=position
  253.    position=position+increment
  254.  
  255.  
  256. /* Etape III */
  257.  
  258. Pour i=0 a n-1 faire :
  259.    val=octet(Tab1[i].Z);
  260.  
  261.    pos=tab2[val];             /* on en deduit la position. */
  262.    tab2[val]=tab2[val]+1;
  263.  
  264.    tab3[pos]=Tab1[i].Numero_de_face /* on place la donnee a la bonne pos */
  265.  
  266.  
  267. V Optimisation
  268. ---------------
  269.  
  270. Comme je l'ai deja dit plus haut, ce tri est typiquement fait pour les demos
  271. pour une raison tres simple : il s'ecrit formidablement bien en Assembleur!
  272.  
  273. C'est un pur bonheur... Roudoudou en a fait une implementation, et celle-ci
  274. fait 84 lignes... Mais ce n'est pas a moi de vous expliquer comment coder
  275. ce tri en ASM...
  276.  
  277.  
  278. Je vais neanmoins donner quelques tips :
  279.  
  280. 1) Remplacez les positions par des pointeurs (des offsets quoi).
  281. En effet, si dans le Tableau 2, vous remplacez la valeur 17 par exemple, par
  282. l'adresse de la case 17 dans Tab3, vous gagnerez en temps lors de la 3eme
  283. etape. Cela s'implemente tres facilement si vous regardez l'algo de l'etape 2.
  284. au depart, position=offset Tab3
  285. puis a l'interieur, position=position+increment*4  Et voila!
  286.  
  287. 2) Le Byte Sort c'est bien, mais le Word Sort, c'est mieux.
  288. En effet, on effectue les 3 etapes 4 fois avec le byte sort, alors que le
  289. Word Sort permet de ne les effectuer que 2 fois... Le principe :
  290. on utilise un Tab2 de 65536 cases (256 Ko), pour trier les valeurs sur
  291. 16 bits.
  292.  
  293. Sachant que tout le monde a 8 Mo maintenant (sur PC), on voit l'interet...
  294. On pourrait meme trier sur 24 bits seulement, ce qui fait un traitement en
  295. une passe, et ce qui ne consomme que 16 Mo :-)  (pour l'an 2006 je pense)
  296. Et pour les petits veinards de l'an 2996, en une passe : 4 Go de Memoire :-)
  297.  
  298.  
  299. 3) Ce tri ne marche malheureusement pas pour les entiers signes (j'ai oublie
  300. de le dire). Donc, en entree de la routine, ajoutez 128 (ou 32768) a toutes
  301. vos valeurs, et en sortie, faites l'inverse...
  302. (Sauf si il y a une meilleure methode, ce qui ne m'etonnerais pas... Si vous
  303. en avez une, faites le moi savoir!)
  304.  
  305.  
  306. Voila, c'est fini maintenant. J'espere que vous avez a peu pres compris.
  307. Et si vous avez des remarques, n'hesitez pas : un mail, ou venez sur #demofr!
  308.  
  309.  - Phar / Flower Corp.